package dataStructure;

import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 哈夫曼树研究测试
 *
 * @author Beney
 */
public class Huffman {
    private Node root = null;
    private final Queue<Node> pq;

    /**
     * 哈夫曼节点类
     */
    public static class Node implements Comparable<Node> {
        Node parent;
        Node left, right;
        String val;
        int freq;

        public Node(Node f, Node l, Node r) {
            this.parent = f;
            this.left = l;
            this.right = r;
        }

        public Node(Node l, Node r) {
            this.left = l;
            this.right = r;
        }

        public Node(int freq, String val) {
            this.freq = freq;
            this.val = val;
        }

        public int compareTo(Node o) {
            return this.freq - o.freq;
        }
    }

    public Huffman(List<Node> nodeList) {
        pq = new PriorityQueue<>();
        pq.addAll(nodeList);
        createHuffman();
    }

    public Node getRoot() {
        return this.root;
    }

    public static void displayCode(Node n, String code) {
        if (n == null)
            return;
        else if (n.left == null && n.right == null)
            System.out.println(n.val + ", value:" + n.freq + ", huffman code:" + code);
        displayCode(n.left, code + "0");
        displayCode(n.right, code + "1");
    }

    private void createHuffman() {
        while (pq.size() > 1) {
            Node n1 = pq.poll();
            Node n2 = pq.poll();
            Node nextNode = new Node(n1, n2);
            nextNode.freq = n1.freq + n2.freq;
            n1.parent = nextNode;
            n2.parent = nextNode;
            pq.add(nextNode);
        }
        if (pq.size() == 1)
            root = pq.poll();
    }

}
